from typing import List


class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        m = len(matrix)
        n = len(matrix[0])
        mn = m * n
        i = 0  # denotes layer i
        flag = 0
        pos = 0
        res = []
        
        while pos < mn:
            # 排除 top row 长度为 1 产生的 edge case
            if flag == 0 and n == 2*i + 1:
                flag = 1
            if flag == 0:  # top row
                res.append(matrix[i][i+pos-(2*i*(m+n)-4*i*i)])
                pos += 1
                if pos == (2*i*(m+n)-4*i*i) + (n-2*i-1):
                    flag = 1
            elif flag == 1:  # right col
                res.append(matrix[i+pos-(2*i*(m+n)-4*i*i)-(n-2*i-1)][n-i-1])
                pos += 1
                if pos == (2*i*(m+n)-4*i*i) + (n-2*i-1) + (m-2*i-1):
                    flag = 2
            elif flag == 2:  # bottom row
                res.append(matrix[m-i-1][i+(n-2*i-1) - (pos-(2*i*(m+n)-4*i*i)-(n-2*i-1)-(m-2*i-1))])
                pos += 1
                if pos == (2*i*(m+n)-4*i*i) + 2*(n-2*i-1) + (m-2*i-1):
                    flag = 3
            else:  # left col
                res.append(matrix[i+m-i-1-(i+pos-(2*i*(m+n)-4*i*i)-2*(n-2*i-1)-(m-2*i-1))][i])
                pos += 1
                if pos == (2*i*(m+n)-4*i*i) + 2*(n-2*i-1) + 2*(m-2*i-1):
                    flag = 0
                    i += 1
        return res
    
    def spiralOrderBetter(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)  # 削头（第一层）
            matrix = list(zip(*matrix))[::-1]  # 将剩下的逆时针转九十度，等待下次被削
        return res


if __name__ == "__main__":
    soln = Solution()
    print(soln.spiralOrder([[]]))
    print(soln.spiralOrder([[1]]))
    print(soln.spiralOrder([[1,5]]))
    print(soln.spiralOrder([[3],[2]]))
    print(soln.spiralOrder([[1,2,3],[4,5,6]]))
    print(soln.spiralOrder([[1,2],[3,4],[5,6]]))
    print(soln.spiralOrder([[1,2,3],[4,5,6],[7,8,9]]))
    print(soln.spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]]))
    print(soln.spiralOrder([[2,3,4],[5,6,7],[8,9,10],[11,12,13]]))
    print(soln.spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]))
    print(soln.spiralOrder([[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]]))
